# -*- coding: utf-8 -*-
# @Time: 2021/8/13 15:20
# @File: problem-876.py
# @DESC: https://leetcode-cn.com/problems/middle-of-the-linked-list/

from list_node_common import ListNode, listToNode


class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        print("返回中间节点")
        i = 0
        cur = head
        dict = {}
        while cur:
            dict[i] = cur
            print(cur.val)
            cur = cur.next
            i += 1
        return dict[int((i)/2)]
    #快慢指针
    def middleNodeV2(self, head: ListNode) -> ListNode:
        p = head
        q = head
        while p and p.next:
            p = p.next.next
            q = q.next
        return q


data = [1, 2, 3, 4, 5]
l = listToNode(data)
so = Solution()
result = so.middleNodeV2(l)
print()
